#include <iostream>  
#include <vector>  
using namespace std;  
  
bool is_valid(vector<int>& cols, int row, int col) {  
    for (int i = 0; i < row; i++) {  
        if (cols[i] == col || abs(cols[i] - col) == abs(i - row))
            return false;
    }  
    return true;  
}  
  
void backtrack(vector<int>& cols, int row, vector<vector<string>>& res) {  
    if (row == cols.size())
        string board(cols.size(), ' ');  
        for (int i = 0; i < cols.size(); i++) {  
            board[cols[i]] = 'Q';  
        }
        res.push_back(board);  
        return;
    for (int col = 0; col < cols.size(); col++) {  
        if (is_valid(cols, row, col))
            cols[row] = col;  
            backtrack(cols, row + 1, res);  
            cols[row] = -1;
}

vector<vector<string>> solve_n_queens(int n) {  
    vector<int> cols(n);  
    vector<vector<string>> res;  
    backtrack(cols, 0, res);  
    return res;  
}
  
int main() {  
    int n = 4;
    vector<vector<string>> res = solve_n_queens(n);  
    for (int i = 0; i < res.size(); i++) {  
        cout << "Solution " << i + 1 << ":" << endl;  
        cout << res[i][0] << endl;
        for (int j = 1; j < res[i].size(); j++) {
            cout << res[i][j] << endl;  
        }  
    }  
    return 0;  
}